1. Field of the Invention
The present invention is directed to a method and apparatus for characterizing or recognizing alphanumeric text characters particularly hand printed text characters and, more particularly, to an automated system in which a least squares pattern recognition method is iterated to produce a classification weight matrix using error correction feedback in which recognition test results are used to replicate (or increase the training weight of) poorly classified characters and to provide negative feedback for incorrect classifications, and where the resulting weight matrix is then used in automated identification processing of hand printed forms or characters or the on-line identification of characters entered on pen-based computers.
2. Description of the Related Art
Conventional methods of character pattern recognition, whether of machine printed characters or hand printed characters, fall into many classes including neural network based recognizers and statistical classifiers as well as template matching and stroke based methods.
Neural network based systems are characterized by plural nonlinear transfer functions which vary in accordance with some learning method, such as back propagation. The neural networks typically evolve discrimination criteria through error feedback and self organization. Because plural transfer functions are used in the educated recognition system, neural networks are not very well suited for implementation on general purpose computers and generally need dedicated special purpose processors or dedicated node hardware in which each of the transfer functions is implemented.
On the other hand, statistical based classifiers are more suited for implementation on general purpose computers. Statistical classifiers can be implemented using a number of different statistical algorithms. These algorithms generally deal with selected features of the characters and analytically determine whether the features belong to or are members of clusters of features which clusters define characteristics of the characters being recognized. In other words, if the features of an unlabeled character fall within the boundaries of a cluster of features which characterize a particular text character, then the probability is high that the character to be labeled corresponds to the character of the cluster.
One approach to identifying whether an unlabeled character falls within a cluster boundary is to compute the Hamming distance between an unlabeled character pixel array and the arrays of possible matching text characters. Another approach is to use a polynomial least mean square classifier with a quadratic discriminant function, such as described in Uma Shrinivasan, "Polynomial Discriminant Method For Hand Written Digit Recognition", State University of New York at Buffalo, Technical Report, Dec. 4, 1989, incorporated by reference herein.
The Shrinivasan classifier works as follows. A database of labeled, hand written alphanumeric characters (digits, upper case alphabetics, or the combination of the two) are converted to feature vectors, v, and are associated with target vectors. The components of the feature vectors are F quadratic polynomials (features) formed from the character's pixel array to provide evidences of lines through the image. The target vector for each character is a standard unit vector e.sub.k(v) with the k(v).sup.th component equal to 1 and all other components equal to zero, where k(v) is the externally provided classification for the character, for example 0,1,2, . . . ,9 or A,B, . . . ,Z or a combination. Standard numerical techniques are used to determine an FxK floating point weight matrix A to minimize the squared errors, .SIGMA..sub.v (Av-e.sub.k(v)).sup.2, where the sum runs over all feature vectors and K is the number of classes, for example 10 digits or 26 alphamerics. The weights matrix, A, is then used to classify unlabeled characters by determining the largest component in the product Aw, where w is the unknown character's feature vector. Additional details of this method can be found in the above-identified paper which includes source code implementing the method.
The above described system along with other statistically based systems, such as described in U.S. Pat. No. 5,060,279, are one shot learning systems, that is, the weight matrix or equivalent database is created in a single pass over the set of labeled characters used to produce the matrix or database. Such statistically based classifiers provide a reasonably good classification system but generally do not have the accuracy of neural network systems. However, the more accurate neural network based systems are slower to learn, slower to identify characters and require more memory and computing hardware than the statistical classifiers. What is needed is a system which combines the advantageous accuracy of the neural network based systems with the speed and efficiency of the statistically based systems and which may be based on simple integer or bit arithmetic.